#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

namespace bit {
	typedef int STDataType;
	typedef struct Stack {
		STDataType* a;
		int top;
		int capacity;
	}ST;

	void STInit(ST* ps, int n);
	void STDestory(ST* ps);
	void STPush(ST* ps, STDataType x);
	void STpop(ST* ps);
	STDataType STTop(ST* ps);
	bool STEmpty(ST* ps);
}

namespace bit {
	void STInit(ST* ps, int n) {
		assert(ps);
		ps->a = (STDataType*)malloc(n * sizeof(STDataType));
		ps->top = 0;
		ps->capacity = n;
	}

	void STPush(ST* ps, STDataType x) {
		assert(ps);
		id(ps->top == ps->capacity) {
			int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
			STDataType* tmp = (STDataType*)realloc(ps->a,  newcapacity * sizeof(STDataType));
			if (tmp == NULL) {
				perror("realloc fail");
				return;
			}
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
		ps->a[ps->top] = x;
		ps->top++;
	}
}


namespace bit {
	typedef int STDataType;
	typedef struct Stack {
		STDataType* a;
		int top;
		int capacity;
	};
	void STInit(ST* ps, int n);
	void STDestory(ST* ps);
	void STPush(ST* ps, STDataType x);
	void STPop(ST* ps);
	STDataType STTop(ST* ps);
	int STSize(ST* ps);
	bool STEmpty(ST* ps);
}

namespace bit {
	void STInit(ST* ps, int n) {
		assert(ps);
		ps->a = (STDataType*)malloc(n * sizeof(STDataType));
		ps->top = 0;
		ps->capacity = n;
	}
	void STPush(ST* ps, STDataType x) {
		assert(ps);
		if (ps->top == ps->capacity) {
			int newcapacity = ps->capacity = 0 ? 4 : ps->capacity * 2;
			STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
			if (tmp == NULL) {
				perror("realloc");
				return;
			}
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
		ps->a[ps->top] = x;
		ps->top++;
	}
}

namespace bit {
	typedef int QDataType;
	typedef struct QueueNode {
		QueueNode* val;
		QueueNode* next;
	}QNode;
	typedef struct Queue {
		QNode* phead;
		QNode* ptail;
		int size;
	}Queue;

	void QueueInit(Queue* pq);
	void QueueDestopry(Queue* pq);
	void QueuePush(Queue* pq, QDataType x);
	void QueuePop(Queue* pq);
	QDataType QueueFront(Queue* pq);
	QDataType QueueBack(Queue* pq);
	bool QueueEmpty(Queue* pq);
	int QueueSize(Queue* pq);
}

namespace bit {
	void QueueInit(Queue* pq) {
		assert(pq);
		pq->phead = NULL;
		pq->ptail = NULL;
		pq->size = 0;
	}
}